lib/Mi manual de algoritmos/version_world_finals_2009/src/dp/particion_troncos.cpp

   1 /*
   2   O(n^3)
   3  dp[i][j] = Mínimo costo de partir la cadena entre las
   4  particiones i e j, ambas incluídas.
   5 */
   6 int dp[1005][1005];
   7 int p[1005];
   8
   9 int cubic(){
  10   int n, m;
  11   while (scanf("%d %d", &n, &m)==2){
  12     p[0] = 0;
  13     for (int i=1; i<=m; ++i){
  14       scanf("%d", &p[i]);
  15     }
  16     p[m+1] = n;
  17     m += 2;
  18
  19     for (int i=0; i<m; ++i){
  20       dp[i][i+1] = 0;
  21     }
  22
  23     for (int i=m-2; i>=0; --i){
  24       for (int j=i+2; j<m; ++j){
  25         dp[i][j] = p[j]-p[i];
  26         int t = INT_MAX;
  27         for (int k=i+1; k<j; ++k){
  28           t = min(t, dp[i][k] + dp[k][j]);
  29         }
  30         dp[i][j] += t;
  31       }
  32     }
  33
  34     printf("%d\n", dp[0][m-1]);
  35   }
  36   return 0;
  37 }
  38
  39
  40 /*
  41   O(n^2)
  42
  43   dp[i][j] = Mínimo costo de partir la cadena entre las
  44   particiones i e j, ambas incluídas.  pivot[i][j] = Índice de
  45   la partición que usé para lograr dp[i][j].
  46  */
  47 int dp[1005][1005], pivot[1005][1005];
  48 int p[1005];
  49
  50 int quadratic(){
  51   int n, m;
  52   while (scanf("%d %d", &n, &m)==2){
  53     p[0] = 0;
  54     for (int i=1; i<=m; ++i){
  55       scanf("%d", &p[i]);
  56     }
  57     p[m+1] = n;
  58     m += 2;
  59
  60     for (int i=0; i<m-1; ++i){
  61       dp[i][i+1] = 0;
  62     }
  63     for (int i=0; i<m-2; ++i){
  64       dp[i][i+2] = p[i+2] - p[i];
  65       pivot[i][i+2] = i+1;
  66     }
  67
  68     for (int d=3; d<m; ++d){ //d = longitud
  69       for (int j, i=0; (j = i + d) < m; ++i){
  70         dp[i][j] = p[j] - p[i];
  71         int t = INT_MAX, s;
  72         for (int k=pivot[i][j-1]; k<=pivot[i+1][j]; ++k){
  73           int x = dp[i][k] + dp[k][j];
  74           if (x < t) t = x, s = k;
  75         }
  76         dp[i][j] += t, pivot[i][j] = s;
  77       }
  78     }
  79
  80     printf("%d\n", dp[0][m-1]);
  81   }
  82   return 0;
  83 }